/*
有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

 

示例 1：

输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
 [1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
 [0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
 [0,0,0,0]]
因此，结果为 [2] 。
示例 2：

输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0],
 [1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0], 
 [1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
 [0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同

*/

#include "stdc++.h"

/* 逆向思维 + 并查集
消除一个砖块的效果是：一个连通分量被分成了两个连通分量；
并查集的作用是：把两个连通分量合并成一个连通分量。
考虑：补上被击碎的砖块以后，有多少个砖块因为这个补上的这个砖块而与屋顶的砖块相连。
*/
class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n, 0);
        size.resize(n, 0);
        for (int i{0}; i < n; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    }
    int getSize(int x) {
        int root = find(x);
        return size[root];
    }
private:
    vector<int> parent;
    vector<int> size; // 与当前index连通的数量
};
class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        rows = grid.size();
        cols = grid[0].size();
        // 第一步：把grid中的砖头全部几岁
        vector<vector<int>> copy{grid}; // 备份grid
        for (const auto& hit : hits) {
            copy[hit[0]][hit[1]] = 0; // 在copy中敲碎hits中的砖头
        }
        // 第二步：建图
        int size = rows * cols; // size是图的大小，size表示虚拟的「屋顶」在并查集中的编号
        UnionFind* uf = new UnionFind(size + 1);
        for (int j{0}; j < cols; ++j) {
            if (copy[0][j] == 1) {
                uf->unite(j, size); // 将下标为0的这一行与屋顶相连
            }
        }
        for (int i{1}; i < rows; ++i) {
            for (int j{0}; j < cols; ++j) {
                if (copy[i][j] == 1) {
                    if (copy[i - 1][j] == 1) {
                        // 如果上方也是砖块，就合并
                        uf->unite(getIndex(i - 1, j), getIndex(i, j));
                    }
                    if (j >= 1 && copy[i][j - 1] == 1) {
                        // 如果左边也是砖块，合并
                        uf->unite(getIndex(i, j - 1), getIndex(i, j));
                    }
                }
            }
        }
        // 第三步：按照hits的逆序，在copy中补回砖块，把每一次因为补回砖块而与屋顶项链的砖块的增量记录下来
        int hitsSize = hits.size();
        vector<int> ret(hitsSize, 0);
        for (int i{hitsSize - 1}; i >= 0; --i) {
            int x = hits[i][0];
            int y = hits[i][1];
            if (grid[x][y] == 0) {
                continue; // 如果传入的grid中这一块就是空白，那么hit也不会产生任何影响
            }
            int oldNum = uf->getSize(size); // 补回之前与屋顶相连的砖块数
            if (x == 0) {
                uf->unite(y, size); // 如果补回的这个结点在第 1 行，要告诉并查集它与屋顶相连（逻辑同第 2 步）
            }
            // 在4个方向上看一下，如果相邻的4个方向上有砖块，合并
            for (const auto& dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (inArea(newX, newY) && copy[newX][newY] == 1) {
                    uf->unite(getIndex(x, y), getIndex(newX, newY));
                }
            }
            int curNum = uf->getSize(size); // 补回之后与屋顶相连的砖块数
            ret[i] = max(0, curNum - oldNum - 1); // 减去的 1 是逆向补回的砖块（正向移除的砖块），与 0 比较大小，是因为存在一种情况，添加当前砖块，不会使得与屋顶连接的砖块数更多
            copy[x][y] = 1; // 真正补回这个砖块
        }
        return ret;
    }
    // 二维坐标转换为一维
    int getIndex(int x, int y) {
        return x * cols + y;
    }
    // 判断二维坐标是否越界
    bool inArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
private:
    int rows;
    int cols;
    const vector<vector<int>> dirs {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };
};